package ljl.alg.jianzhioffer.round3.hard;

import java.util.Comparator;
import java.util.PriorityQueue;

public class _41_MedianFinder {

    PriorityQueue<Integer> upper = new PriorityQueue<>();
    PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder());

    public void addNum(int num) {
        // 一样多，往上放，放之前，过一遍下面
        if (upper.size() == lower.size()) {
            lower.offer(num);
            upper.offer(lower.poll());
        }
        // 上面多，往下放，放之前，先过一遍上面，把小的弄下去
        else {
            upper.offer(num);
            lower.offer(upper.poll());
        }
        // 下面不会多，因为一样时会往上放，要么一样，要么上面多一个
    }

    public double findMedian() {
        if (upper.size() > lower.size()) return upper.peek();
        return (upper.peek() + lower.peek()) / 2.0;
    }

}
